package com.atguigu.huffmantree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr={13,7,8,3,29,6,1};

        Node root = create(arr);

        root.preOrder();

    }

    public static Node create(int[] arr){
        List<Node> nodeList=new ArrayList<>();
        for (int i : arr) {
            nodeList.add(new Node(i));
        }


        while(nodeList.size()>1){
            Collections.sort(nodeList);

            Node node1 = nodeList.get(0);
            Node node2 = nodeList.get(1);

            Node parentNode = Node.calcParentNode(node1, node2);

            nodeList.remove(node1);
            nodeList.remove(node2);
            nodeList.add(parentNode);
        }

        return nodeList.get(0);

    }


}

class Node implements Comparable<Node>{
    public int value;
    public Node left;
    public Node right;

    public Node(int value) {
        this.value = value;
    }

    public void preOrder(){
        System.out.println(this);

        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(Node o) {
        return this.value-o.value;
    }

    public static Node calcParentNode(Node node1,Node node2){
        Node parent = new Node(node1.value + node2.value);
        parent.left=node1;
        parent.right=node2;
        return parent;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
